package com.example.demo.suanfa_jiegou;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: java_base
 * @description: 反转单 、双链表
 * @author: zhouhongtao
 * @happyCreateTime: 2022/02/09 14:40
 */
public class ReverseSingleLinked {



    @Test
    public void reverseSingle(){
        // 创建数据
        SingleNode singleNode5 = new SingleNode(5);
        SingleNode singleNode4 = new SingleNode(4,singleNode5);
        SingleNode singleNode3 = new SingleNode(3,singleNode4);
        SingleNode singleNode2 = new SingleNode(2,singleNode3);
        SingleNode singleNode1 = new SingleNode(1,singleNode2);
        // 循环输出链表
        SingleNode header = singleNode1;
//        do {
//            if (header != null){
//                System.out.println(header.value);
//                header = header.next;
//            }
//        }while(header != null );
//        while(header != null){
//            System.out.println(header.value);
//            header = header.next;
//        }
//        System.out.println(header);
        SingleNode reverseedHeader =  reverseSingle02(header);
//        System.out.println(reverseedHeader);
        while(reverseedHeader != null){
            System.out.println(reverseedHeader.value);
            reverseedHeader = reverseedHeader.next;
        }
//        System.out.println(reverseedHeader);
    }

    /**
     * 优解
     * 这个函数 返回值 为下一个节点
     * @param head
     * @return
     */
    public SingleNode reverseSingle(SingleNode head){
        SingleNode pre = null;
        SingleNode next = null;

        while (head != null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        System.out.println("");

        System.out.println(pre);
        return pre;
    }

    public SingleNode reverseSingle02(SingleNode head){
        if (head == null){
            return null;
        }
        SingleNode header = null;
        List<SingleNode> contains = new ArrayList<>();
        while (head != null) {
            contains.add(head);
            head = head.next;
        }

        contains.get(0).next = null;
//        int N = contains.size();
//        for (int i = 0; i <N; i++) {
//            contains.get(i).next = contains.get(i - 1);
//        }

        for (int i = 1; i < contains.size() ; i++) {
            SingleNode cur = contains.get(i);
            SingleNode pre = contains.get(i - 1);
            cur.next = pre;
        }

        System.out.println(contains.get(contains.size() - 1));
        return contains.get(contains.size() - 1);
    }

    // 生成随机 单链表
    public SingleNode generateRandomLinkedList(int len,int value){
        int size = (int) (Math.random() * (len + 1));
        if (size == 0) {
            return null;
        }
        size--;
        SingleNode head = new SingleNode((int) (Math.random() * (value + 1)));
        SingleNode pre = head;
        while (size!=0){
            SingleNode cur = new SingleNode((int) (Math.random() * (value + 1)));
            pre.next = cur;
            pre = cur;
            size--;
        }
        return head;
    }


    /**
     *     单链表
     */
    class SingleNode<T>{
        public T value ;
        private SingleNode next;
        private SingleNode(T value){
            this.value = value;
        }
        private SingleNode(T value,SingleNode next){
            this.value = value;
            this.next = next;
        }

        @Override
        public String toString() {
            return "SingleNode{" +
                    "value=" + value +
                    ", next=" + next +
                    '}';
        }
    }



}


